#include "shellSort.h"
#include "util.h"
#include "sortCommon.h"

static bool _is_Hsorted(int a[], int n, int h)
{
    for(int i = h; i < n; i++)
    {
        if(_less(a[i], a[i-h]))
            return false;
    }

    return true;
}

static void _shellSort(int a[], int n)
{
    int h = 1;
    while(h < n / 3)
        h = 3 * h + 1;

    while(h >= 1)
    {
        for(int i = h; i < n; i++)
        {
            for(int j = i; j >= h && _less(a[j], a[j-h]); j -= h)
            {
                _exch(a, j, j-h);
            }
        }
        UTIL_ASSERT(_is_Hsorted(a, n, h));
        h /= 3;
    }

    UTIL_ASSERT(_is_array_sorted(a, n));
}

void shellSort(int a[], int n)
{
    UTIL_ASSERT(a != nullptr);
    UTIL_ASSERT(n >= 1);
    _shellSort(a, n);
}
